\relax 
\bibstyle{abbrv}
\citation{genome_sequence_0}
\citation{genome_sequence_1}
\citation{genome_sequence_2}
\citation{genome_sequence_3}
\citation{genome_sequence_4}
\citation{roche454}
\citation{illumina}
\citation{solid}
\citation{tools}
\citation{Burrows94ablock-sorting}
\citation{Ferragina07compressedrepresentations}
\citation{bwa}
\citation{soap2}
\citation{mrFast}
\citation{shrimp}
\citation{mrFast}
\@LN@col{1}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{sec:introduction}{{1}{1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Next-generation DNA sequencing}{1}}
\@LN@col{2}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}DNA Sequencing tools}{1}}
\@LN@col{1}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}New Algorithm: FastHash}{2}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Background}{2}}
\newlabel{sec:background}{{2}{2}}
\@LN@col{2}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Burrows-Wheeler transform based aligning tools}{2}}
\newlabel{bwt}{{2.1}{2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.1}Prefix tree and string matching}{2}}
\newlabel{prefix_tree}{{2.1.1}{2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.2}Burrows-Wheeler transform and backward searching}{2}}
\newlabel{bwt_bs}{{2.1.2}{2}}
\citation{saruman}
\citation{needleman}
\citation{ukkonen}
\@LN@col{1}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Hash-table based aligning tools}{3}}
\newlabel{hash_tool}{{2.2}{3}}
\@LN@col{2}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}Hash-table query}{3}}
\newlabel{hash_query}{{2.2.1}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}String Compares}{3}}
\newlabel{string_compre}{{2.3}{3}}
\@LN@col{1}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}FastHASH}{4}}
\newlabel{fast_hash}{{2.4}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Algorithm Optimization}{4}}
\newlabel{sec:algorithm}{{3}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Adjacency Filtering}{4}}
\newlabel{sec:af}{{3.1}{4}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces The coordinate entry size\relax }}{4}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{fig:entry_size}{{1}{4}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces The number of edit-distance performs and pass\relax }}{4}}
\newlabel{fig:edit_dist}{{2}{4}}
\@LN@col{1}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Adjacency Filtering for exact match\relax }}{5}}
\newlabel{fig:ad_1}{{3}{5}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Adjacency Filtering for inexact match\relax }}{5}}
\newlabel{fig:ad_2}{{4}{5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Cheap Key Selection}{5}}
\newlabel{sec:cheapkey}{{3.2}{5}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.1}Pigeon Hole theorem and multiple search keys}{5}}
\@LN@col{1}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.2}Avoid duplicated Adjacency filtering at using multiple searching keys}{6}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Error distribution \& required number of keys\relax }}{6}}
\newlabel{fig:pigeon}{{5}{6}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Adjacency Filtering Distribution\relax }}{6}}
\newlabel{fig:key_dist}{{6}{6}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.3}Imbalance of the number of key entry size}{6}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Cheap Key Selection Mechanism\relax }}{6}}
\newlabel{fig:cheap_key}{{7}{6}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.4}Cheap Key Selection}{6}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Cheap Key Selection Result\relax }}{6}}
\newlabel{fig:ck_result}{{8}{6}}
\@LN@col{1}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces Efficiency of Cheap Key Selection\relax }}{7}}
\newlabel{fig:key_dist2}{{9}{7}}
\@writefile{toc}{\contentsline {section}{\numberline {4}GPU Implementation}{7}}
\newlabel{sec:gpu}{{4}{7}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces GPU flow chart\relax }}{7}}
\newlabel{fig:gpu}{{10}{7}}
\@LN@col{1}
\@writefile{toc}{\contentsline {section}{\numberline {5}methodology}{8}}
\newlabel{sec:methodology}{{5}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Hash table \& Key size}{8}}
\newlabel{sec:method_hash}{{5.1}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Input fragment set}{8}}
\newlabel{sec:medhod_input}{{5.2}{8}}
\@LN@col{2}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Hardware environment}{8}}
\newlabel{sec:method_hw}{{5.3}{8}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Nvidia Tesla C2070 Specification.\relax }}{8}}
\newlabel{table:tesla}{{1}{8}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces The data structure of detail error\relax }}{8}}
\newlabel{fig:detail_error}{{9}{8}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Evaluation}{8}}
\newlabel{sec:evaluation}{{6}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}The goal and quality of sequencing process}{8}}
\@LN@col{1}
\@writefile{lof}{\contentsline {figure}{\numberline {11}{\ignorespaces The data structure of detail error\relax }}{9}}
\newlabel{fig:detail_error}{{11}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}CPU evaluation and Result}{9}}
\@writefile{lof}{\contentsline {figure}{\numberline {12}{\ignorespaces The total sequencing time of CPU implementations\relax }}{9}}
\newlabel{fig:cpu_result}{{12}{9}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {13}{\ignorespaces The total sequencing time of CPU implementations\relax }}{9}}
\newlabel{fig:gpu_portion}{{13}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3}GPU evaluation and Result}{9}}
\@writefile{lof}{\contentsline {figure}{\numberline {14}{\ignorespaces The total sequencing time of CPU and GPU implementations\relax }}{9}}
\newlabel{fig:gpu_result}{{14}{9}}
\@LN@col{1}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.4}FastHASH vs. BWA}{10}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Analysis}{10}}
\newlabel{sec:analysis}{{7}{10}}
\@writefile{lof}{\contentsline {figure}{\numberline {15}{\ignorespaces The total sequencing time of FastHASH and BWA\relax }}{10}}
\newlabel{fig:bwa}{{15}{10}}
\@LN@col{2}
\bibdata{ref}
\bibcite{mrFast}{1}
\bibcite{solid}{2}
\bibcite{illumina}{3}
\bibcite{saruman}{4}
\bibcite{Burrows94ablock-sorting}{5}
\bibcite{genome_sequence_2}{6}
\@LN@col{1}
\@writefile{lof}{\contentsline {figure}{\numberline {16}{\ignorespaces The number of Adjacency Filtering performs   (9 base-pairs Hash table vs. 12 base-pairs Hash table)\relax }}{11}}
\newlabel{fig:c0912_af}{{16}{11}}
\@writefile{lof}{\contentsline {figure}{\numberline {17}{\ignorespaces The number of edit-distance calculation performs   (9 base-pairs Hash table vs. 12 base-pairs Hash table)\relax }}{11}}
\newlabel{fig:c0912_ed}{{17}{11}}
\@writefile{lof}{\contentsline {figure}{\numberline {18}{\ignorespaces The sequencing speed   (9 base-pairs Hash table vs. 12 base-pairs Hash table)\relax }}{11}}
\newlabel{fig:c0912_speed}{{18}{11}}
\@LN@col{2}
\@writefile{lof}{\contentsline {figure}{\numberline {19}{\ignorespaces GPU Analysis\relax }}{11}}
\newlabel{fig:warp}{{19}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Conclusion}{11}}
\newlabel{sec:conclusion}{{8}{11}}
\bibcite{genome_sequence_4}{7}
\bibcite{Ferragina07compressedrepresentations}{8}
\bibcite{bwa}{9}
\bibcite{soap2}{10}
\bibcite{roche454}{11}
\bibcite{needleman}{12}
\bibcite{tools}{13}
\bibcite{shrimp}{14}
\bibcite{genome_sequence_0}{15}
\bibcite{ukkonen}{16}
\bibcite{genome_sequence_1}{17}
\bibcite{genome_sequence_3}{18}
\@LN@col{1}
\@LN@col{2}
